% Calculates wandering distance for G w/ a Monte Carlo method for n samples
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% function wanderingDistanceTable =
% wanderingDistanceMonteCarlo(G,numSamples,varargin);
%  
%   This function will calculate the wandering distance table for input
%   graph G by using a Monte Carlo method.  This effectively is a brute
%   force method for calculating the wandering distance by performing many
%   random walks and averaging the results for each possible vertex
%   combination
%
%   INPUTS:     G - adjacency matrix for graph G
%               numSamples - number of random samples to average
%               
%   OUTPUTS:    wanderingDistanceTable - table of wandering distance values            
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function wanderingDistanceTable = wanderingDistanceMonteCarlo(G,numSamples,varargin);

% A few variable initializations
[xmax ymax]=size(G);
wanderingDistanceTable = zeros(xmax,ymax);
tic
% Think of it as x = start, y = destination
for x = 1:xmax
    for y = 1:ymax
        % Ignore matches because wd is 0 in this case
        if (x == y),
            wanderingDistanceTable(x,y) = 0;
        else            
            % Initialize the accumulator 
            acc = 0;          
            % We'll average over a specified number of samples.     
            for z = 1:numSamples                
                % Reset our starting position
                currentNode = x;
                
                % Keep traveling until we reach the destination node
                while (currentNode ~= y),
                    % Choose a random target move
                    targetMove = randi(xmax);
                    % If a path exists to our target node, move to it
                    if (G(currentNode,targetMove) == 1)
                        currentNode = targetMove;
                        acc = acc + 1;
                    end;                    
                end;               
            end;
            
            % Now let's average the samples
            wanderingDistanceTable(x,y) = acc / numSamples;
        end;        
    end;
end;
toc